//
//  main.cpp
//  189.轮转数组
//
//  Created by Yan Zihao on 2024/10/18.
//

#include <iostream>
#include <vector>
using namespace std;

class Solution1
{
public:
    void rotate(vector<int>& nums, int k)
    {
        int size = nums.size();
        
        for (int j = k; k > 0; k--)
        {
            int last_num = nums[size-1];
            for (int i = size - 1; i >= 1; i--)
            {
                nums[i] = nums[i-1];
            }
            nums[0] = last_num;
        }
    }
};
//我的代码没有问题,但是时间复杂度太大了

//leetcode官方方法1:使用额外的数组
//我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)modn 的位置，最后将新数组拷贝至原数组即可。
class Solution2
{
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        vector<int> newArr(n);
        for (int i = 0; i < n; ++i)
        {
            newArr[(i + k) % n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
};

//leetcode官方方法2:环状替换
class Solution3
{
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start)
        {
            int current = start;
            int prev = nums[start];
            do
            {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
            } while (start != current);
        }
    }
};
